Modern communication networks for mobile communication are organized in cells. As one example, 3GPP Long Term Evolution (LTE) networks organize physical-layer cell-identities in 168 unique physical-layer cell-identity groups (represented by NID(1)=0, . . . , 167), each cell-identity group NID(1) comprising three cell-identities (represented by NID(2)=0, 1, 2), which amounts to a total of 504 cell-identities NCELLID=3NID(1)+NID(2) addressable by a pair of numbers NID(1) and NID(2).
The cell-identity NID(2) is detected in a primary synchronization signal. For detection of the cell-identity group NID(1), an analysis of a secondary synchronization signal (S-SSIG) XS-SSIG involves cross-correlations with all possible S-SSIGs represented by reference signals, each of which indicates a cell-identity group NID(1). A list of correlation peaks that exceed a threshold (and their correlation peak values) is returned as cell-identity group candidates.
A first conventional technique directly implements a definition of the correlation,
                                          c            ⁡                          (                                                N                  ID                                      (                    1                    )                                                  ,                                                      s                                          pos                      ,                                                        ⁢                                      cp                    type                                                              )                                =                                    ∑                              n                =                0                            61                        ⁢                                                            X                                      S                    -                    SSIG                                                        cp                    type                                                  ⁡                                  (                  n                  )                                            ·                                                d                                                            N                      ID                                              (                        1                        )                                                              ,                                          s                      pos                                                                            N                    ID                                          (                      2                      )                                                                      ⁡                                  (                  n                  )                                                                    ,                            (                  Eq          .                                          ⁢          1                )            to assess a set of communication parameters including the cell-identity group NID(1), two possible subframe positions spos (at 0 ms or 5 ms) and two possible cyclic prefix types cptype (normal or extended). The received S-SSIG assuming a cyclic prefix type cptype to be tested is denoted by XS-SSIGcptype and the reference signal is denoted by
      d                  N        ID                  (          1          )                    ,              s        pos                    N      ID              (        2        )              .
The reference signal
  d            N      ID              (        1        )              ,          s      pos            N    ID          (      2      )      is a sequence of elements in {−1, +1}, for which reason products in Eq. 1 between elements of the synchronization signal XS-SSIGcptype(n) and the reference signal
      d                  N        ID                  (          1          )                    ,              s        pos                    N      ID              (        2        )              ⁡      (    n    )  are not implemented by multiplication steps, but as fast sign changes. In the absence of multiplications steps, the computational complexity depends on the number of involved addition steps.
Computation of the correlations requires considerable hardware resources as the synchronization signals occur twice per 10 ms radio frame, and there are numerous combinations of receive signal data and reference signals for each set of communication parameters to be evaluated. The computational complexity of the above implementation requires 2×2×168×62=41 664 steps of addition for evaluating each combination of the two cyclic prefix types (cptype=0, 1), the two subframe timings (spos=0, 1), and the 168 possible cell-identity groups (NID(1)), each evaluation involving 62 additions for correlating corresponding sequences of length l=62. The conventional computation technique thus consumes considerable battery resources and causes a notable cell search time.
A more advanced implementation exploits an alternating structure of the standard definition of the reference signals
      d                  N        ID                  (          1          )                    ,              s        pos                    N      ID              (        2        )              .Computation of the correlation c(NID(1),spos,cptype) is split up in two partial correlations of even-numbered elements with a first reference signal
      d                  N        ID                  (          1          )                    ,              s        pos                    N      ID              (        2        )              ⁡      (          2      ⁢                          ⁢      n        )  and odd-numbered elements with a second reference signal
      d                  N        ID                  (          1          )                    ,              s        pos                    N      ID              (        2        )              ⁡      (                  2        ⁢                                  ⁢        n            +      1        )  of length l/2=31:
      c    ⁡          (                        N          ID                      (            1            )                          ,                  s          pos                ,                  cp          type                    )        =                    ∑                  n          =          0                30            ⁢                                    X                          S              ⁢                              -                            ⁢              SSIG                                      cp              type                                ⁡                      (                          2              ⁢                                                          ⁢              n                        )                          ·                              d                                          N                ID                                  (                  1                  )                                            ,                              s                pos                                                    N              ID                              (                2                )                                              ⁡                      (                          2              ⁢                                                          ⁢              n                        )                                +                  ∑                  n          =          0                30            ⁢                                    X                          S              ⁢                              -                            ⁢              SSIG                                      cp              type                                ⁡                      (                                          2                ⁢                                                                  ⁢                n                            +              1                        )                          ·                                            d                                                N                  ID                                      (                    1                    )                                                  ,                                  s                  pos                                                            N                ID                                  (                  2                  )                                                      ⁡                          (                                                2                  ⁢                                                                          ⁢                  n                                +                1                            )                                .                    
According to the standard definition of 3GPP Technical Specification TS 36.211 (V8.2.0, 2008-03) in Sect. 6.11.2.1 for the reference signals
      d                  N        ID                  (          1          )                    ,              s        pos                    N      ID              (        2        )              ,independently evaluable subsequences for the odd- and even-numbered elements of the reference signals
  d            N      ID              (        1        )              ,          s      pos            N    ID          (      2      )      are:
                    d                              N            ID                          (              1              )                                ,                      s            pos                                    N          ID                      (            2            )                              ⁡              (                  2          ⁢                                          ⁢          n                )              =                                        s                          m              x                                ⁡                      (            n            )                          ·                              c            0                          N              ID                              (                2                )                                              ⁡                      (            n            )                              =                        d                      m            x                                N            ID                          (              2              )                                      ⁡                  (                      2            ⁢                                                  ⁢            n                    )                      ,wherein a first parameter mx=mspos(NID(1)) depends on the communication parameters cell-identity group, NID(1), and the subframe position, spos; and
                    d                              N            ID                          (              1              )                                ,                      s            pos                                    N          ID                      (            2            )                              ⁡              (                              2            ⁢                                                  ⁢            n                    +          1                )              =        ⁢                                        s                          m              y                                ⁡                      (            n            )                          ·                              c            1                          N              ID                              (                2                )                                              ⁡                      (            n            )                          ·                              z                                          m                x                            ⁢              mod              ⁢                                                          ⁢              8                                ⁡                      (            n            )                              =            ⁢                        d                                                    m                x                            ⁢              mod              ⁢                                                          ⁢              8                        ,                          m              y                                            N            ID                          (              2              )                                      ⁡                  (                                    2              ⁢                                                          ⁢              n                        +            1                    )                      ,wherein a second parameter is my=m1-spos(NID(1)) and the first parameter mx=mspos(NID(1)) enters modulo 8. Integer-valued functions m0(NID(1)) and m1(NID(1)) are defined in document 3GPP TS 36.211.
Given the previously determined value of NID(2), there are M=31 different first reference signals
  d      m    x        N    ID          (      2      )      parameterized by mx=0, . . . , 30. Furthermore, there are 8×M different second reference signals
  d            m      x      ′        ,          m      y            N    ID          (      2      )      parameterized by m′x=0, . . . , 7 and my=0, . . . , 30. A pair (mx, my) of the first parameter mx and the second parameter my (with my≠mx) results from the correlation analysis. The pair (mx, my) uniquely determines the pair (N1D(1),spos) of physical-layer communication parameters: In case mx<my, spos=0 and (mx, my)=(m0, m1) determines the cell-identity group NID(1) according to Table 6.11.2.1-1 in 3GPP TS 36.211 (V8.2.0, 2008-03). Otherwise, if mx>my, spos=1 and (my, mx)=(m0, m1) determines NID(1).
Accordingly, there is a total of (1+8)×M first and second reference signals, and the partial correlations with the receive signal XS-SSIGcptype for the two cyclic prefix types (cptype) require adding up the l/2=31 elements, which amounts to 2×(1+8)×M×31 additions for each partial correlation. Adding the results of the two partial correlations to obtain the (full) correlation for each of the 168×2×2 possible sets (NID(1),spos,cptype) of communication parameters requires one addition for each set. Hence, the total number of additions is reduced to 2×9×31×31+168×2×2=17 970.
From “A New Cell Search Scheme in 3GPP Long Term Evolution Downlink OFDMA Systems”, Wireless Communications & Signal Processing, 2009, a cell search procedure in 3GPP LTE downlink systems is known. In a first step of the procedure, a coarse symbol timing, and fractional Carrier Frequency Offset (CFO) is detected in order to process the frequency-domain data. In a second step after acquiring the symbol timing, an integer CFO and a sector cell index NID(2) are simultaneously detected by cross-correlating the received frequency-domain data with Primary Synchronization Channel (P-SCH) signals. In a third step, the frame timing and cell-identity group NID(1) are detected using the Secondary Synchronization Channel (S-SCH) signal and the information about NID(2) deduced in the second step.
In US 2008/0273522 A1 various techniques for generating synchronization signals based on a M-sequence in order to convey cell parameters (e.g., cell IDs) are taught. In one embodiment, the secondary synchronization signal is based on two cyclic shifted M-sequences with a length of N=31, wherein the cyclic shifts are indicative of the cell ID. The secondary synchronization signal generated in such a way may be processed at a user terminal UE, in order to detect the cell-identity group NID(1) by using the cell index NID(2) and performing a M-sequence Transform (FMT) on two input sequences which correspond to those two M-sequence based sequences of the generated synchronization signal.